package top101K.linkedList;

import java.util.List;

/**
 * @Author quan
 * @Description 链表内指定区间反转
 * @Date 2023/7/24 20:24
 */
public class Demo2_ReverseBetween {
    /**
     * 要求：1——>2——>3——>4——>5——>NULL，给定m=2，n=4，返回1——>4——>3——>2——>5——>NULL
     * @param head 头结点
     * @param m 反转的开始位置
     * @param n 反转的结束位置
     * @return
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //定义虚拟头结点，避免要反转的子链表的前驱为空
        ListNode dummyHead = new ListNode(-1);
        //虚拟头结点和链表相连接
        dummyHead.next = head;
        //定义pre指针，指向要被反转的子链表的最左端节点的前驱
        ListNode pre = dummyHead;
        //遍历走到要反转的子链表：其中左节点走到子链表的前驱，右节点走到给定n值的子链表的对应节点位置
        for (int i = 0; i < m-1; i++) {
            pre = pre.next;
        }
        ListNode right = pre;
        for (int i = 0; i < n-m+1; i++) {
            right = right.next;
        }
        //找到被反转链表的最后一个节点的下一个节点保存：cur
        ListNode cur = right.next;
        //找到被反转链表的左节点:也就是头结点
        ListNode left = pre.next;
        //子链表反转
        reverse(left);
        //将反转后的链表与最左端和最右端的链表拼接
        pre.next = right;
        left.next = cur;
        //返回头结点
        return dummyHead.next;
    }

    private void reverse(ListNode head) {
        //pre表示前一个结点，初始化为null
        ListNode pre = null;
        //当前节点指针
        ListNode cur = head;
        //循环迭代
        while (cur!=null){
            //存储当前cur节点的下一个节点
            ListNode cur_next = cur.next;
            //更改指针到前一个结点
            cur.next = pre;
            //此时的前一个结点就为pre了
            //更新pre值
            pre = cur;
            //更新当前节点指针
            cur = cur_next;
        }
    }
}
